import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-10-16
 * Time:1:03
 */

class MyLinkedList {
    static class Node {
        public int val;
        public Node prev;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;
    public Node last;

    public void addLast(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = last = node;
        }
        last.next = node;
        node.prev = last;
        last = last.next;
    }

    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}

public class Test {
    //将递归转化为循环 - 逆序打印链表
    //递归方式
    public static void printList(MyLinkedList.Node head) {
        if (head != null) {
            printList(head.next);
            System.out.print(head.val + " ");
        }
    }

    //循环的方式
    public static void printList1(MyLinkedList.Node head) {
        if (head == null) {
            return;
        }
        Stack<MyLinkedList.Node> stack = new Stack<>();
        //将链表中的节点保存到栈中
        MyLinkedList.Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //将栈中的元素出栈
        while (!stack.empty()) {
            System.out.print(stack.pop().val + " ");
        }
    }
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        System.out.print("逆序前：");
        list.display();

        //递归方式逆序
        System.out.print("递归方式逆序后：");
        printList(list.head);

        System.out.println();

        //循环方式-采用Stack栈方式
        System.out.print("循环方式-Stack方式逆序后：");
        printList1(list.head);
    }
    public static void main3(String[] args) {
        //链表也可以实现栈
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
    public static void main2(String[] args) {
        MyStack stack = new MyStack();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);

        System.out.println(stack.size());//4

        System.out.println(stack.pop());//45
        System.out.println(stack.peek());//34

        System.out.println(stack.size());//3
    }
    public static void main1(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //push - 入栈/压栈
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);
        System.out.println(stack);

        System.out.println("出栈前的元素个数："+stack.size());
        //pop - 将栈顶元素出栈
        System.out.println("将栈顶元素"+" "+stack.pop()+" "+"出栈");//45
        System.out.println("出栈后的元素个数："+stack.size());
        //peek - 获取栈顶元素
        System.out.println("此时的栈顶元素:"+stack.peek());//34
    }
}
